package algorithm.math;

import algorithm.model.ListNode;

/**
 * leetcode : https://leetcode.com/problems/add-two-numbers/description/
 * Difficulty : Medium
 *
 * 两个数字相加，数字用链表表示。由左到右依次表示从低位到高位
 * @Author Antony
 * @Since 2018/7/13 22:38
 */
public class AddTwoNumbers {

    public static void main(String[] args) {
//        ListNode n1 = ListNode.initDate(new int[]{2,4,3});
//        ListNode n2 = ListNode.initDate(new int[]{5,6,4});

//        ListNode n1 = ListNode.initDate(new int[]{5});
//        ListNode n2 = ListNode.initDate(new int[]{5});
//        System.out.println(addTwoNumbers(n1, n2));
//        System.out.println(addTwoNumbers_recursion(n1, n2));

    }

    // 递归解法还没搞明白，有空再考虑吧
    public static ListNode addTwoNumbers_recursion(ListNode l1, ListNode l2) {
        return null;
    }


    /**
     * 非递归
     * 大数相加，注意进位。
     * 并且在完成时注意是否还有进位要处理，如果有，则需要在高位前加1
     * beats 98.74% - 27ms
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode initNode = new ListNode(0);
        ListNode first = initNode;
        int n1,n2,tmp;
        while(l1!=null || l2!=null){
            if(l1==null){
                n1 = 0;
            }else {
                n1 = l1.val;
                l1 = l1.next;
            }
            if(l2==null){
                n2=0;
            }else{
                n2 = l2.val;
                l2 = l2.next;
            }
            tmp = n1+n2+carry;
            if(tmp >= 10){
                tmp -=10;
                carry=1;
            }else {
                carry=0;
            }
            initNode.next = initNode = new ListNode(tmp);
        }
        if(carry >0){
            initNode.next = initNode = new ListNode(1);
        }

        return first.next;
    }


    public static ListNode addTwoNumbers_test(ListNode l1, ListNode l2) {
        int carry = 0;  // 进位
        ListNode initNode = new ListNode(0);    // 往后走的指针节点
        ListNode first = initNode;                 // 头节点
        int n1,n2,tmp;
        while(l1!=null || l2!=null){
            n1 = l1==null ? 0 : l1.val;
            n2 = l2==null ? 0 : l2.val;
            l1 = l1==null ? null : l1.next;
            l2 = l2==null ? null : l2.next;
            tmp = n1 + n2 + carry;
            if(tmp >= 10){
                tmp -= 10;
                carry = 1;
            }else{
                carry = 0;
            }
            initNode.next = new ListNode(tmp);
            initNode = initNode.next;
        }
        if(carry > 0){
            initNode.next = new ListNode(1);
        }
        return first.next;
    }
}
